package com.qz.stack;



import java.util.Scanner;

/**
 * @Description
 * @Author Flag
 * @Date: 2021/7/20 8:53
 * @Version: 1.0
 **/
public class LinkedStackDome {
    public static void main(String[] args) {
        //测试一下LinkedStack是否正常
        //先创建一个ArrayStack对象->表示栈
        LinkedStack stack = new LinkedStack(4);
        String key = "";
        boolean loop = true;//用于控制是否退出
        Scanner scanner = new Scanner(System.in);
        while (loop){
            System.out.println("show:表示显示栈");
            System.out.println("exit:退出程序");
            System.out.println("push:表示添加元素到栈(入栈)");
            System.out.println("pop:表示从栈取出数据(出战)");

            System.out.println("请输入你的选择:");
            key = scanner.next();

            switch (key){
                case "show":
                    stack.show();
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                case "push":
                    System.out.println("请输入一个数字");
                    int i = scanner.nextInt();
                    stack.push(i);
                    break;
                case "pop":
                    try{
                        int pop = stack.pop();
                        System.out.println("出栈的数据:"+pop);
                    } catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }


        }

    }

}

class LinkedStack{
    //定义栈的大小
    private int maxSize;
    //链表模拟栈，
    private LinkedStackNode first;
    //top表示栈顶，初始化是-1
    private int top;

    /**
     * 构造方法
     * @param maxSize 栈的大小
     */
    public LinkedStack(int maxSize) {
        this.maxSize = maxSize;
        top = -1;
    }

    /**
     * 判断栈是否满了
     * @return
     */
    public boolean isFull(){
        return top+1 == maxSize;
    }

    /**
     * 入栈
     * @param value 入栈的元素
     */
    public void push(int value){
        //1、判断栈是否满了
        if(this.isFull()){
            System.out.println("栈已经满了,不能再添加元素");
            return;
        }

        //2、新创建一个节点，用于添加到链表上
        LinkedStackNode node = new LinkedStackNode(value);

        //3、将top++,表示链表中的元素新增了一个
        top++;

        //4、判断头元素是否为null,如果是null,代表是第一个元素,则直接让新元素当第一个元素
        if(first == null){
            first = node;
            return;
        }

        //5.如果头元素不是null,则证明，此时链表中已经有元素，则将新元素添加上即可
        //5.1获取到链表的尾部
        LinkedStackNode middleNode = first;
        while (middleNode.getNext() != null){
            middleNode = middleNode.getNext();
        }
        //5.2将链表添加上去
        middleNode.setNext(node);
    }


    /**
     * 出栈
     * @return 出栈的元素
     */
    public int pop(){
        //1.判断栈是否为null
        if(this.isEmpty()){
            throw new RuntimeException("栈中没有元素");
        }

        //2.将链表的数量减一
        top -- ;

        //3.如果链表中是否只有一个元素
        if(first.getNext() == null){
            LinkedStackNode popNode = this.first;
            this.first = null;
            return popNode.getNumber();
        }


        //4.如果链表中有不只一个元素
        //4.1.定义一个中间变量，让他指向链表的最后一个元素，即最后要出栈的元素
        LinkedStackNode lastNode = first;

        //4.2.定义一个中间变量，用来用来获取到比lastNode前一个元素,‘
        //因为是单向链表，我们出栈后，要置空指向最后一个元素的指针，所以需要找到最有一个元素的前一个元素进行操作
        LinkedStackNode beforeLastNode = null;


        //4.2.遍历链表,直到lastNode是最后一个元素,此时，如果链表中只有一个元素，则
        while (lastNode.getNext() != null){
            //将lastNode给到beforeLastNode
            //然后lastNode向后移动
            //此时就构造出 beforeLastNode在lastNode前一个位置的情况
            beforeLastNode = lastNode;
            lastNode = lastNode.getNext();
        }
        //4.3.此时将最后一个元素的前一个元素的next指针变成null,则相当于舍弃掉了最后一个元素
        beforeLastNode.setNext(null);
        //4.3.返回lastNode的编号
        return lastNode.getNumber();
    }


    /**
     * 显示栈的元素
     */
    public void show(){
        //判断栈是否为null
        if(this.isEmpty()){
            System.out.println("栈中无元素");
            return;
        }

        //定义一个新的链表节点
        LinkedStackNode newLinedStackHead = null;

        //正向遍历原始链表，将链表的每一个元素，都放到新的链表的第一个元素
        //因为前面做了判断，所以first不可以为null
        LinkedStackNode oldLinkedStackNode = first;
        //直到原始链表元素为null时，结束
        while (oldLinkedStackNode != null){

            LinkedStackNode middleNode = new LinkedStackNode(oldLinkedStackNode.getNumber());

            if(newLinedStackHead == null){
                newLinedStackHead = middleNode;
            } else {

                middleNode.setNext(newLinedStackHead);
                newLinedStackHead = middleNode;
            }

            //移动原始链表的位置
            oldLinkedStackNode = oldLinkedStackNode.getNext();
        }

        while (newLinedStackHead != null){
            System.out.println(newLinedStackHead.getNumber());
            newLinedStackHead = newLinedStackHead.getNext();
        }



    }

    /**
     * 判断栈是否为null
     * @return 结果
     */
    public boolean isEmpty(){
        return top == -1;
    }
}

/**
 * 链表栈的节点
 */
class LinkedStackNode{
    private int number;
    private LinkedStackNode next;


    public LinkedStackNode(int number) {
        this.number = number;
    }



    public int getNumber() {
        return number;
    }


    public LinkedStackNode getNext() {
        return next;
    }

    public void setNext(LinkedStackNode next) {
        this.next = next;
    }
}